package com.interview.javabasic.DataStructrue;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

public class Queen8 {
    //定义有多少人皇后
    int max = 8;
    //定义数组，放置位置的结果
    int[] arr = new int[max];
    static int count=0;
    public static void main(String[] args) {
        //测试8皇后
        Queen8 queen8 = new Queen8();
        queen8.check(0);
        System.out.printf("一共有%d种解法。",count);

    }

    //放置第n个皇后
    //特别注意check每一次递归式，都有一套for循环
    private void check(int n){

        if (n==max){
            print();
            count++;
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前的皇后n,放到该行的第一列
            arr[n] = i;
            if (judge(n)){
                //不冲突,及开始递归
                check(n+1);
            }
        }
    }

    //查看放置第n个皇后，检测该皇后是否和前面已经存在的皇后冲突
    private boolean judge(int n){
        for (int i = 0;i<n;i++){
            //!!!!!判断是否在同一列或者在同一行
            if (arr[i] == arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }

    //写一个方法,将皇后摆放的位置输出
    private void print(){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
